최소 신장 트리 == 최소 가중치 신장 트리 (Minimum Spanning Tree)모든 정점을 연결하며 전체 가중치의 합이 최소화하는 비순환 부분 집합
- Kruskal Algorithm
- Prim Algorithm
( 위 두 알고리즘을 그리디 알고리즘을 기반으로 한다. )
safe edge: 최소 신장 트리의 부분집합 A에 대해서
A∪{(u,v)}도 최소 신장 트리의 부분 집합이 되도록 하는
간선 (u,v)
안전 간선(safe edge)
절단 (S, V-S)가 최소 신장 트리에 포함되는 E의 부분 집합 A를 존중하고,
(u, v)가 교차하는 경량 간선인 경우, (u, v)는 A에 대해 안전 간선이다.
포리스트의 트리가 하나가 될 때까지 안전 간선을 추가하는 루프를 반복하면, 최소 신장 트리를 얻을 수 있다.
- 희소 그래프의 최소 신장 트리
- 병목 신장 트리(bottleneck spanning tree)